import heapq
import copy
from collections import deque

class EightPuzzle:
    def __init__(self, initial_state, goal_state):
        """
        初始化8数码问题求解器
        :param initial_state: 初始状态，3x3的二维列表，0表示空格
        :param goal_state: 目标状态，3x3的二维列表
        """
        self.initial_state = initial_state
        self.goal_state = goal_state
        self.rows = 3
        self.cols = 3
        
    def find_zero(self, state):
        """
        找到空格(0)的位置
        :param state: 当前状态
        :return: 空格的行列坐标
        """
        for i in range(self.rows):
            for j in range(self.cols):
                if state[i][j] == 0:
                    return i, j
        return None
    
    def get_neighbors(self, state):
        """
        获取当前状态的所有可能下一步状态
        :param state: 当前状态
        :return: 所有可能的下一步状态列表
        """
        neighbors = []
        zero_row, zero_col = self.find_zero(state)
        
        # 四个可能的移动方向：上、下、左、右
        moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        move_names = ['上', '下', '左', '右']
        
        for i, (dr, dc) in enumerate(moves):
            new_row, new_col = zero_row + dr, zero_col + dc
            
            # 检查新位置是否在边界内
            if 0 <= new_row < self.rows and 0 <= new_col < self.cols:
                # 创建新状态
                new_state = copy.deepcopy(state)
                # 交换空格和相邻数字
                new_state[zero_row][zero_col], new_state[new_row][new_col] = \
                    new_state[new_row][new_col], new_state[zero_row][zero_col]
                neighbors.append((new_state, move_names[i]))
                
        return neighbors
    
    def states_equal(self, state1, state2):
        """
        比较两个状态是否相等
        """
        for i in range(self.rows):
            for j in range(self.cols):
                if state1[i][j] != state2[i][j]:
                    return False
        return True
    
    def state_to_tuple(self, state):
        """
        将状态转换为元组，用于哈希表存储
        """
        return tuple(tuple(row) for row in state)
    
    def print_state(self, state):
        """
        打印状态
        """
        for row in state:
            print("+---+---+---+")
            print("|", end="")
            for val in row:
                if val == 0:
                    print("   |", end="")
                else:
                    print(f" {val} |", end="")
            print()
        print("+---+---+---+")
    
    def print_path(self, path):
        """
        打印解路径
        """
        for i, (state, action) in enumerate(path):
            print(f"步骤 {i}:")
            if action:
                print(f"动作: 空格向{action}移动")
            self.print_state(state)
            print()

    def dfs(self, max_depth=30):
        """
        深度优先搜索
        :param max_depth: 最大搜索深度，防止无限搜索
        :return: 解路径或None
        """
        stack = [(self.initial_state, [], 0)]  # (状态, 路径, 深度)
        visited = set()
        
        while stack:
            current_state, path, depth = stack.pop()
            
            # 检查是否达到目标状态
            if self.states_equal(current_state, self.goal_state):
                return path + [(current_state, None)]
            
            # 检查深度限制
            if depth >= max_depth:
                continue
                
            # 检查是否已访问过该状态
            state_tuple = self.state_to_tuple(current_state)
            if state_tuple in visited:
                continue
            visited.add(state_tuple)
            
            # 获取邻居状态
            for neighbor_state, action in self.get_neighbors(current_state):
                neighbor_tuple = self.state_to_tuple(neighbor_state)
                if neighbor_tuple not in visited:
                    new_path = path + [(current_state, action)]
                    stack.append((neighbor_state, new_path, depth + 1))
        
        return None  # 未找到解
    
    def bfs(self):
        """
        广度优先搜索
        :return: 解路径或None
        """
        queue = deque([(self.initial_state, [], 0)])  # (状态, 路径, 深度)
        visited = set()
        
        while queue:
            current_state, path, depth = queue.popleft()
            
            # 检查是否达到目标状态
            if self.states_equal(current_state, self.goal_state):
                return path + [(current_state, None)]
            
            # 检查是否已访问过该状态
            state_tuple = self.state_to_tuple(current_state)
            if state_tuple in visited:
                continue
            visited.add(state_tuple)
            
            # 获取邻居状态
            for neighbor_state, action in self.get_neighbors(current_state):
                neighbor_tuple = self.state_to_tuple(neighbor_state)
                if neighbor_tuple not in visited:
                    new_path = path + [(current_state, action)]
                    queue.append((neighbor_state, new_path, depth + 1))
        
        return None  # 未找到解
    
    def manhattan_distance(self, state):
        """
        计算曼哈顿距离启发式函数
        """
        distance = 0
        for i in range(self.rows):
            for j in range(self.cols):
                if state[i][j] != 0:
                    value = state[i][j]
                    # 找到目标位置
                    goal_pos = None
                    for x in range(self.rows):
                        for y in range(self.cols):
                            if self.goal_state[x][y] == value:
                                goal_pos = (x, y)
                                break
                        if goal_pos:
                            break
                    # 计算曼哈顿距离
                    distance += abs(i - goal_pos[0]) + abs(j - goal_pos[1])
        return distance
    
    def a_star(self):
        """
        A*启发式搜索算法
        :return: 解路径或None
        """
        # 优先队列：(f_score, state, path, g_score)
        heap = [(self.manhattan_distance(self.initial_state), 
                 self.initial_state, [], 0)]
        visited = {}
        
        while heap:
            f_score, current_state, path, g_score = heapq.heappop(heap)
            
            # 检查是否达到目标状态
            if self.states_equal(current_state, self.goal_state):
                return path + [(current_state, None)]
            
            state_tuple = self.state_to_tuple(current_state)
            # 如果已经访问过且之前的g_score更优，则跳过
            if state_tuple in visited and visited[state_tuple] <= g_score:
                continue
            visited[state_tuple] = g_score
            
            # 获取邻居状态
            for neighbor_state, action in self.get_neighbors(current_state):
                neighbor_tuple = self.state_to_tuple(neighbor_state)
                new_g_score = g_score + 1
                
                # 如果邻居状态未被访问过，或找到了更优路径
                if neighbor_tuple not in visited or new_g_score < visited[neighbor_tuple]:
                    new_path = path + [(current_state, action)]
                    h_score = self.manhattan_distance(neighbor_state)
                    f_score = new_g_score + h_score
                    heapq.heappush(heap, (f_score, neighbor_state, new_path, new_g_score))
        
        return None  # 未找到解

def main():
    # 定义初始状态和目标状态
    initial_state = [
        [2, 8, 3],
        [1, 6, 4],
        [7, 0, 5]
    ]
    
    goal_state = [
        [1, 2, 3],
        [8, 0, 4],
        [7, 6, 5]
    ]
    
    # 创建8数码问题求解器
    puzzle = EightPuzzle(initial_state, goal_state)
    
    print("8数码问题求解器")
    print("初始状态:")
    puzzle.print_state(initial_state)
    print("目标状态:")
    puzzle.print_state(goal_state)
    print("\n" + "="*50 + "\n")
    
    # 使用深度优先搜索
    print("1. 使用深度优先搜索(DFS)求解...")
    solution = puzzle.dfs(max_depth=20)
    if solution:
        print(f"DFS找到解，共{len(solution)-1}步:")
        puzzle.print_path(solution)
    else:
        print("DFS在指定深度内未找到解")
    print("\n" + "="*50 + "\n")
    
    # 使用广度优先搜索
    print("2. 使用广度优先搜索(BFS)求解...")
    solution = puzzle.bfs()
    if solution:
        print(f"BFS找到解，共{len(solution)-1}步:")
        puzzle.print_path(solution)
    else:
        print("BFS未找到解")
    print("\n" + "="*50 + "\n")
    
    # 使用A*启发式搜索
    print("3. 使用A*启发式搜索求解...")
    solution = puzzle.a_star()
    if solution:
        print(f"A*找到解，共{len(solution)-1}步:")
        puzzle.print_path(solution)
    else:
        print("A*未找到解")

if __name__ == "__main__":
    main()